#include <iostream>
#include <vector>
#include <stdlib.h>
#include <set>
#include <assert.h>
#include <algorithm>
#include <deque>
#include <iterator>

using namespace std;

class Heap {
  public:
    deque<int> store_;

    Heap()
	    : store_( 1 ) {
    }

    void push( int i ) {
	store_.push_back( i );
	sift_up();
    }

    void pop() {
	if ( empty() ) throw "stop it";
	store_[1] = store_.back();
	store_.pop_back();
	sift_down();
    }

    int top() const {
	if ( empty() ) throw "stop it";
	return store_[1];
    }

    unsigned size() const { return store_.size() - 1; }
    unsigned empty() const { return store_.size() == 1; }

  private:

    unsigned left_child( unsigned i ) const {
	return 2*i;
    }

    unsigned right_child( unsigned i ) const {
	return 2*i+1;
    }

    unsigned parent( unsigned i ) const {
	return i / 2;
    }

    unsigned bottom() const {
	return size();
    }

    void swap( unsigned i, unsigned j ) {
	int t = store_[i];
	store_[i] = store_[j];
	store_[j] = t;
    }

    void sift_up() {
	unsigned i = bottom();
	while ( i > 1 && store_[ i ] > store_[ parent( i )] ) {
	    swap( i, parent( i ) );
	    i = parent( i );
	}
    }

    void sift_down() {
	unsigned i = 1;
	while ( i < bottom() ) {
	    unsigned new_i = i;
	    if ( right_child( i ) <= bottom() &&
		 store_[ right_child( i ) ] > store_[ i ] ) {
		new_i = right_child( i );
	    }
	    if ( left_child( i ) <= bottom() && 
		 store_[ left_child( i ) ] > store_[ new_i ] ) {
		new_i = left_child( i );
	    }
	    if ( i == new_i ) break;
	    swap( i, new_i );
	    i = new_i;
	}
    }
};

unsigned left_child( unsigned i ) {
    return i * 2 + 1;
}
unsigned right_child( unsigned i ) {
    return i * 2 + 2;
}

unsigned parent( unsigned i ) {
    return ( i - 1 ) / 2;
}

void swap( int *a, int *b ) {
    const int t = *a;
    *a = *b;
    *b = t;
}

void sift_down( int *begin, int* end ) {
    assert( end >= begin );
    const unsigned last( end - begin );
    unsigned i = 0;
    while ( i < last ) {
	unsigned new_i = i;
	const unsigned left( left_child( i ) );
	const unsigned right( right_child( i ) );
	if ( right < last && begin[ right ] > begin[ new_i ] ) {
	    new_i = right;
	}
	if ( left < last && begin[ left ] > begin[ new_i ] ) {
	    new_i = left;
	}
	if ( i == new_i ) break;
	swap( begin+i, begin+new_i );
	i = new_i;
    }
}

void make_heap( int* begin, int* end ) {
    int *cursor = end-1;
    while ( cursor >= begin ) {
	sift_down( cursor, end );
	cursor--;
    }
}

void heap_sort( int* begin, int* end ) {
    make_heap( begin, end );
    int *cursor = end-1;
    while ( cursor > begin ) {
	swap( begin, cursor );
	sift_down( begin, cursor );
	cursor--;
    }
}

void reverse( int *begin, int *end ) {
    for ( int i = 0; i < (end-begin)/2; i++ ) {
	swap( begin+i, end-i-1 );
    }
}

int main( int argc, char*argv[] ){

    Heap h;
    vector<int> input;

    cout << "Input : ";
    for ( int i = 0; i < 11; i++ ) {
	const int r = rand() % 100;
	h.push( r );
	input.push_back( r );
	cout << r << " ";
    }
    cout << endl;

    cout << "Class : ";
    while ( !h.empty() ) {
    	cout << h.top() << " "; h.pop();
    }
    cout << endl;

    cout << "Func  : ";
    heap_sort( &input[0], &input[input.size()-1]+1 );
    copy( input.begin(), input.end(), ostream_iterator< int >( cout, " " ));
    cout << endl;
	  
    cout << "Rever : ";
    reverse( &input[0], &input[input.size()-1]+1 );
    copy( input.begin(), input.end(), ostream_iterator< int >( cout, " " ));
    cout << endl;
    return 0;
}
